package com.ljzn;

public class Solution {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node4 = new ListNode(4);
        ListNode node6 = new ListNode(6);
        ListNode node3 = new ListNode(3);
        ListNode node7 = new ListNode(7);
        
        node1.next = node4;
        node4.next = node6;
        node6.next = node3;
        node3.next = node7;

        ListNode res = oddEvenList(node1);

        while(res != null){
            System.out.print(res.val + " ");
            res = res.next;
        }
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public static ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        ListNode res = dummy;

        ListNode odd = head;
        ListNode even = head.next;

        ListNode pre = null;
        while (odd != null){
            ListNode tempN = new ListNode(odd.val);
            dummy.next = tempN;
            dummy = dummy.next;
            pre = tempN;

            if(odd.next != null){
                odd = odd.next.next;
            }else{
                tempN.next = null;
                odd = odd.next;
            }
        }

        while (even != null){
            ListNode tempN = new ListNode(even.val);
            pre.next = tempN;
            pre = pre.next;
            if(even.next != null){
                even = even.next.next;
            }else{
                tempN.next = null;
                even = even.next;
            }
        }

        return res.next;
    }
    
    public static class ListNode {
      int val;
      ListNode next = null;
      public ListNode(int val) {
        this.val = val;
      }
    }
}